%Przegląd algorytmów stosowanych do rozwiązywania problemu opisywanych
%we współczesnej literaturze

% TODO - reorganizacja + jakies linki do opisów algorytmów

\section{Algorytmy}

Opierając się na znalezionel literaturze prezentujemy krótki przegląd algorytmów wykorzystywanych do rozwiązywania problemu SameGame.

\subsection{Przegląd algorytmów}

W publikacji naukowej ''Solving SameGame and its Chessboard Variant'' \cite{samegame-solving} opisano kilka sposobów rozwiązania problemu, oraz przeprowadzono szereg symulacji pozwalających na ich porównanie.

\subsubsection{Brute force}

Ze względu na złożoność problemu, uwzględniając wielki rozmiar planszy do gry, oraz większą ilość kolorów, metoda brute force nie przynosi rozwiązania w zadowalającym czasie. Podobnie zachowują się algorytmy zachłanne. Również algorytmy wykorzystujące metody podziału i ograniczeń (np. algorytm Alfa-Beta) nie sprawdzają się w rozwiązaniu problemu. Spowodowane jest to tym, że wymagają one bardzo dobrej estymacji wartości podjęcia danego kroku, co jest praktycznie niemożliwe. Różne usprawnienia algorytmu nie przyniosły spodziewanych rezultatów. Ponadto usprawnienia te mogą prowadzić do błędnych rozwiązań, nie pozwalających na ukończenie gry. 

\subsubsection{Beam Search}

Kolejnym rozważanym algorytmem pojawiającym się w literaturze jest Beam-Search. Jest to heurystyczny algorytm polegający na optymalizacji algorytmu Best-First. Algorytm polega na przeszukiwaniu grafu przewidując najbardziej obiecujące kolejne posunięcia [można dać odnośnik do linku na wikipedii]. 

\subsubsection{Algorytm bankiera}

Algorytm Bankiera przydziela pewien budżet dla każdego wierzchołka grafu przeszukiwania. Zagłębianie się w kolejne kroki rozwiązania jest możliwe tylko wtedy gdy budżet nie został jeszcze w całości wydany. W przeciwnym wypadku przeszukiwanie staje się zachłanne. 

\subsubsection{Przeszukiwanie Monte Carlo}

Przeszukiwanie Monte Carlo jest pewnym wariantem algorytmu Best-First przeszukującego graf. Przeszukiwanie to nie polega jednak na wyliczaniu wartości funkcji estymacyjnej, a na przeprowadzeniu pewnej liczby symulacji dla danego wierzchołka. Wartość jakości rozwiązania polega na aktualnym stanie planszy. 

Zaproponowane rozwiązanie przez autorów publikacji optymalizuje algorytm Monte Carlo. Wariant ten nazwano Monte Carlo z wybieraniem ruletkowym. Optymalizacja polega na próbie utworzenia jak największych bloków dla różnych kolorów. 

\subsubsection{Algorytm SP-MCTS}

Obecnie jedną z najpopularniejszych metod rozwiązywania problemów typu SameGame jest Single-Player Monte Carlo Tree Search(SP-MCTS) wraz z Cross-Entropy Method(CEM) \cite{cross-entropy-solving}.

Monte-Carlo Tree Search (MCTS) to algorytm wyszukiwania. W dzisiejszych czasach jest używany do wyznaczania najlepszych ruchów w takich grach jak Go. Metoda świetnie znajduje zastosowanie w grach, gdzie trudno jest wyznaczyć funkcję oceny. Przykłady : Go, SameGame. Przyczyną wybrania Cross-Entropy Method (CEM) jest to, że metoda dobrze się sprawdziła w podkręcaniu[naprawianiu] parametrów MCTS dla gry Go.

SP-MCTS może być użyta na 2 sposoby:
\begin{itemize}
	\item konstrukcja drzewa dla całej gry
	\item konstrukcja drzewa dla każdego kroku
\end{itemize}

Algorytm z konstrukcją drzewa dla każdego kroku daje lepsze wyniki.

Każdemu węzłowi odpowiada pozycja na planszy. Każdy węzeł przechowuje swój licznik odwiedzin i wartość. MCTS składa się z czterech faz: selection, simulation, expansion i backpropagation. Fazy są powtarzane póki nie skończy się czas. Krok zagrania – syn korzenia o największej wartości.

Fazy:
\begin{itemize}
	\item Selection – faza definiująca sposób poruszania się w drzewie od korzenia do liścia. Musi być balans pomiędzy wykorzystaniem dobrych ruchów a znalezieniem nowych.
	\item Simulation – zaczyna się wtedy, gdy poprzednia faza dochodzi do liścia. Wtedy uruchamia się losowa gra.
	\item Expansion – faza dodająca jeden lub więcej węzłów do drzewa. Węzeł do dodania – pierwsza napotkana pozycja na planszy której jeszcze nie ma w drzewie. Jeśli licznik odwiedzin przekracza pewien próg, wszystkie pozostałe dzieci zostaną dodane.
	\item Backpropagation – propagująca wyniki gry(wygrane czy przegrane) wstecz od liścia do wszystkich węzłów które są na ścieżce od korzenia do tego liścia. Wartość węzła – to średnia wartości wyników.
\end{itemize}

\subsubsection{Cross-Entropy Method}

Cross-Entropy Method (CEM) – ewolucyjno-optymalizacyjna metoda, związana z Estimation-of-Distribution Algorithms (EDAs). Tak samo jak EDAs metoda reprezentuje zbiór możliwych rozwiązań za pomocą parametryzowanego rozkładu prawdopodobieństwa. CEM bardzo często jest porównywana do algorytmów genetycznych, bo też jest metodą ewolucyjną. Największa różnica polega na tym, że algorytmy genetyczne opierają się o populacje, lecz CEM opiera się o model.

Zbieżność CEM do rozwiązania polega na iteracyjnej zmianie parametrów rozkładu prawdopodobieństwa, który reprezentuje zakres możliwych rozwiązań. Iteracja składa się z trzech najważniejszych kroków.
\begin{itemize}
	\item Pierwszym krokiem jest wyznaczenie zbioru S próbek z rozkładu prawdopodobieństwa.
	\item W drugim kroku dla każdej próbki wyznacza się wartość funkcji oceny. Pewną liczbę próbek z największą wartością funkcji oceny nazywamy ''elitarnymi próbkami''
	\item W trzecim kroku ''elitarne próbki'' są używane do modyfikacji rozkładu prawdopodobieństwa.
\end{itemize}

Po tych krokach następuje kolejna iteracja używająca zmieniony poprzednio rozkład prawdopodobieństwa. Powtarzając te kroki, prawdopodobieństwo generowania mniej lub więcej takich samych ''elitarnych próbek'' rośnie.